#include<bits/stdc++.h>
using namespace std;

int n;
int a[5],cur,temp;
int main(){
	cin>>n;
	a[1]=1;
	a[2]=2;
	a[3]=4;
	a[4]=8;
	if(n<=4){
		cout<<a[n];
		return 0;
	}
	for(int i=5;i<=n;i++){
		cur=(a[4]+a[3]+2*a[2]+2*a[1])%1000;
		a[4]=cur;
		a[3]=a[4];
		a[2]=a[3];
		a[1]=a[2];
	}
	cout<<cur;
	return 0;
}
